package com.peng.leetcode.unionFind;

import java.util.PriorityQueue;

/**
 * MinCostConnectPoints
 * 1584. 连接所有点的最小费用
 *
 *
 * @author: lupeng6
 * @create: 2021/1/11 20:51
 */
public class MinCostConnectPoints {

    public static void main(String[] args) {
        int[][] points = {{0, 0}, {2, 2}, {3, 10}, {5, 2}, {7, 0}};
        System.out.println(new MinCostConnectPoints().minCostConnectPoints(points));
    }

    private int[] parent;

    public int minCostConnectPoints(int[][] points) {
        parent = new int[points.length];
        for (int i = 0; i < points.length; i++) {
            parent[i] = i;
        }

        // 小顶堆
        PriorityQueue<Edge> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < points.length - 1; i++) {
            for (int j = i + 1; j < points.length; j++) {
                int[] point1 = points[i];
                int[] point2 = points[j];
                int xi = point1[0];
                int yi = point1[1];

                int xj = point2[0];
                int yj = point2[1];

                int cost = Math.abs(xi - xj) + Math.abs(yi - yj);
                Edge edge = new Edge(i, j, cost);
                priorityQueue.offer(edge);
            }
        }

        int minCost = 0;

        while (!priorityQueue.isEmpty()) {
            Edge edge = priorityQueue.poll();
            int point1 = edge.point1;
            int point2 = edge.point2;
            int cost = edge.len;
            int root1 = find(point1);
            int root2 = find(point2);
            if (root1 != root2) {
                minCost += cost;
                parent[root1] = root2;
            }
        }

        return minCost;
    }


    private int find(int x) {
        while (x != parent[x]) {
            parent[x] = parent[x];
            x = parent[x];
        }
        return x;
    }

    // 两点之间的边
    class Edge implements Comparable<Edge> {
        Integer point1;
        Integer point2;
        Integer len;

        public Edge(Integer point1, Integer point2, Integer len) {
            this.point1 = point1;
            this.point2 = point2;
            this.len = len;
        }

        @Override
        public int compareTo(Edge o) {
            return Integer.compare(len, o.len);
        }
    }
}
